package exercises;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-12
 * Time: 15:44
 */

/**
 *  两个链表的第一个公共结点
 * 链表
 * 描述
 * 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
 *（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
 *
 * 示例1
 * 输入：
 * {1,2,3},{4,5},{6,7}
 * 返回值：{6,7}
 * 说明：
 * 第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
 * 这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
 * 示例2
 * 输入：
 * {1},{2,3},{}
 * 返回值：{}
 * 说明：
 * 2个链表没有公共节点 ,返回null，后台打印{}
 */

public class exercise2 {

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2){
        //1.先分别求出两个链表的长度
        ListNode pl = pHead1;
        ListNode ps = pHead2;
        int lenA = 0;
        int lenB = 0;

        while (pl != null) {
            lenA++;
            pl = pl.next;
        }
        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        //注意pl和ps，指向了null
        pl = pHead1;
        ps = pHead2;

        //2.求差值
        int len = lenA - lenB;

        if (len < 0) {
            pl = pHead2;
            ps = pHead1;
            len = lenB - lenA;//len变为为正数
        }

        //现在知道pl指向长的链表，ps指向短的链表

        //3.操作两个链表pl和ps，长的链表（pl）先走链表的差值，然后再一起走直到相交
        while (len != 0) {
            pl = pl.next;
            len--;
        }

        //两个链表分别都走，直到他们相遇
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }

        if (pl == null) {
            //pl，ps为空,也不可能相交
            return null;
        }

        return pl;
    }
}
